1. The Field of the Invention
The field of the invention is that of generic algorithms. More specifically, the field is genetic algorithms useful for problem solving.
2. The Prior Art
Genetic algorithms provide a method of improving a given set of objects. The processes of natural selection and survival of the fittest provide a theoretical base. Genetic algorithms in their conventional form can solve many problems. However, the problem of the Prisoner's Dilemma illustrates the limitations of conventional genetic algorithms.
The Prisoner's Dilemma is a well-researched problem in game theory (with numerous psychological, sociological, and geopolitical interpretations) in which two players can either cooperate or not cooperate. The players make their moves simultaneously and without communication. Each player then receives a payoff that depends on his move and the move of the other player.
The payoffs in the Prisoner's Dilemma game are arranged so that a non-cooperative choice by one player always yields that player a greater payoff than a cooperative choice (regardless of what the other player does). However, if both players are selfishly non-cooperative, they are both worse off than if they had both cooperated. The game is not a "zero sum game" because, among other things, both players are better off if they both cooperate.
Applying the conventional genetic algorithm to a specific problem requires that a representation scheme be created to represent possible solutions to the problem as an individual chromosome amongst a large population of chromosomes. In the Prior Art, each individual chromosome in this population must take the form of a character string over a fixed alphabet, most typically a presentation of 0's and 1's (i.e. binary "bits") of the same length. The creation of this representation scheme (coding scheme) is an inherent part of the conventional genetic algorithm because the codes undergo manipulation when the genetic algorithm is actually applied.
In the case of a game, an individual in this population is a particular "strategy" for playing the game. A "strategy" for a given player in a game is a way of specifying what move the player is to make at a particular point in a game given all the allowable moves and information about the state of the game which is available to the player. In the case of the Prisoner's Dilemma game, the allowable moves for a particular player are always the same two alternatives--the player can cooperate or not. The information available to the player consists of the history of previous moves from the beginning of the game.
The chapter concerning game playing entitled "The Evolution of Strategies in the Iterated Prisoner's Dilemma" by Robert Axelrod in Genetic Algorithms and Simulated Annealing (1987) illustrates the general nature of conventional genetic algorithms and how they apply to specific problems. In particular, it illustrates the process by which a mathematical problem is converted into a form involving strings of 0's and 1's (i.e. strings of binary "bits") of the same length. Thus the conventional genetic algorithm can be applied to the problem.
In his article on the Prisoner's Dilemma, Axelrod began by noting that there are 4 possible ways the previous play could have occurred (i.e. cooperation or non-cooperation by each of the 2 players). In order to represent this game within the confines of the conventional genetic algorithm, Axelrod decided to base a player's next move only on knowledge of the history of the previous 3 plays. Having made this limitation, there are then 64 possible previous play histories (i.e. 4 times 4 times 4). In this kind of representation scheme, the history of plays by both players for the previous 3 plays are associated with one of the 64 bit positions in a binary string of length 64. For example, bit position 64 might refer to cooperative plays by both players on all 3 previous plays (i.e. previous plays of CCCCCC). A "1" in bit position 64 of this string of length 64 might then instruct the player to cooperate on the current play if the previous plays have been CCCCCC. The entire string of 64 0's and 1's constitutes a complete way of telling the player how to move on the next play based on the history of the previous 3 plays. (In the article, Axelrod actually expands this binary string to length 70 to accommodate 6 special bit positions to deal with the very beginning of the game when there is no history).
After developing the representation scheme, the genetic algorithm begins by randomly creating a population of individual binary strings of length 70. The "fitness" of each of these individual strings (strategies) is then evaluated in an "environment" (which, in this case, consists of a series of different games). In order to play a particular game of the series in this "environment," it is necessary to refer to the appropriate bit position in the string of 70 0's and 1's for each move and then make the indicated move in the game; then, play the entire game; and, then, determine the payoff to the player for the game for following that particular individual strategy. These payoffs are then accumulated (and averaged) over the entire series of games to determine the average fitness of a particular individual strategy. Since each of the 70 bit positions in the binary string of length 70 represent a different past history, the series of games used to evaluate a given individual string would ideally contain a statistically meaningful number of different moves involving each of the 70 past histories.
The genetic algorithm then proceeds by identifying the best individual strategies in the current population and creates offspring for the next generation of individuals using the fittest individual strategies. As in nature, each offspring inherits some genetic traits from each parent in a process of "crossing" some genetic traits from each parent. The process of reproduction by the fittest and crossover tends to produce, over a period of many generations, a population with increasing overall fitness in the environment involved.
Axelrod achieved results from applying the conventional genetic algorithm to the Prisoner's Dilemma game that paralleled other mathematical research and international competitions on how to best play this game. However, it should be noted that the conventional genetic algorithm imposed four important limitations which restrict its usefulness in solving this particular gaming problem and other problems that have been studied.
First, the requirement that each individual in the population be a string of the same length required Axelrod to arbitrarily limit the player considering only a pre-determined number of previous plays (three here) in deciding how to make the next move. This meant possibly ignoring an opponent's previous history of deceitful "surprise attacks" if they occurred more than three moves in the past. Obviously, in many situations, a player whose strategy involves arbitrarily and intentionally ignoring available past history (particularly past history as recent as three moves earlier) would be susceptible to some devastating simple counter-strategies by the opposing player.
Secondly, the use of a binary string (a string of 0's and 1's) led to a representation scheme involving an explosively large number of "different" strategies merely to handle consideration of only the three previous plays (2.sup.70 strategies--over a billion trillion). In contrast, if the representation scheme were not required to be rigidly structured in advance prior to the start of operation of the conventional genetic algorithm, a representation scheme involving only a relative handful of relevant possible histories might have evolved (e.g. "the opponent always cooperates", "the opponent cooperates about half of the time", etc).
Thirdly, the individuals in the population were representational descriptions (codings) of the strategy (as opposed to being actionable procedures which directly made the actual move in the game). Any particular strategy that one envisions and wants to include in the population had to be first coded into a binary string of length 70 before it could be inserted into the population. And, before any play could be made using a strategy, the binary string of length 70 had to be decoded into actionable instructions to make a move in a particular situation.
Fourthly, the binary strings of fixed length provide no hierarchical structure for potential solutions to the problem. The binary string is one dimensional. All items in the string operate at the same level. The significance and desirability of hierarchical structure for solving problems will be seen later.
Whatever the solution's structure, the natural selection process provides a powerful tool for problem solving. This is shown by nature and its various examples of biological entities that survive in various environments. In nature, complex combinations of traits give particular biological populations the ability to adapt, survive, and reproduce in their environments. Equally impressive is the complex, relatively rapid, and robust adaptation and relatively good interim performance that occurs amongst a population of individuals in nature in response to changes in the environment. Nature's methods for adapting biological populations to their environment and nature's method of adapting these populations to successive changes in their environments (including survival and reproduction of the fittest) provides a useful model. This model can develop methods to solve a wide variety of complex problems which are generally thought to require "intelligence" to solve.
In nature, a gene is the basic functional unit by which hereditary information is passed from parents to offspring. Genes appear at particular places (called gene "loci") along molecules of deoxyribose nucleic acid (DNA). DNA is a long thread-like biological molecule that has the ability to carry hereditary information and the ability to serve as a model for the production of replicas of itself. All known life forms on this planet (including bacteria, fungi, plants, animals, and human) are based on the DNA molecule.
The so-called "genetic code" involving the DNA molecule consists of long strings (sequences) of 4 possible gene values that can appear at the various gene loci along the DNA molecule. For DNA, the 4 possible gene values refer to 4 "bases" named adenine, guanine, cytosine, and thymine (usually abbreviated as A, G, C, and T, respectively). Thus, the "genetic code" in DNA consists of a long strings such as CTCGACGGT . . .
When living cells reproduce, the genetic code in DNA is read. Subsequences consisting of 3 DNA bases are used to specify one of 20 amino acids. Large biological protein molecules are, in turn, made up of anywhere between 50 and 500 such amino acids. Thus, this genetic code is used to specify and control the building of new living cells from amino acids.
A chromosome consists of numerous gene loci with a specific gene value (called an "allele") at each gene loci. The chromosome set for a human being consists of 23 chromosomes, and a typical human chromosome contains about 150,000,000 gene values. The 23 human chromosomes together provide the information necessary to describe one individual human being and contain about 3,000,000,000 genes. These 3,000,000,000 genes constitute the so-called "genome" for one particular human being. Complete genomes of the approximately 5,000,000,000 living human beings together constitute the entire pool of genetic information for the human species. It is known that certain gene values occurring at certain places in certain chromosomes control certain traits of the individual, including traits such as eye color, susceptibility to particular diseases, etc. Thus, our current world population of humans can be viewed as a product of a genetic algorithm.
Adaptation in Artificial and Natural Systems, by Professor John H. Holland, summarizes Holland's research in genetic algorithms and presents an overall mathematical theory of adaptation for both natural and artificial systems. A key part of this book described a "genetic algorithm" patterned after nature's methods for biological adaptation. However, a limitation of this work resides in using fixed length binary strings to represent the population. U.S. Pat. No. 4,697,242 (Holland) is an example of a process which uses fixed length binary strings with a genetic algorithm.
Empirical studies by various researchers have demonstrated the capabilities of such genetic algorithms in many diverse areas, including function optimization (De Jong 1980), operation of a gas pipeline (Goldberg 1983), pattern recognition (Englander in Grefenstette, 1985), and many others.
In the chapter entitled "An Overview" contained in the 1987 collection Genetic Algorithms and Simulated Annealing, Lawrence Davis and Martha Steenstrup stated, "In all of Holland's work, and in the work of many of his students, chromosomes are bit strings--lists of 0's and 1's." In addition, they continue, "Some researchers have explored the use of other representations, often in connection with industrial algorithms. Examples of other representations include ordered lists (for bin-packing), embedded lists (for factory scheduling problems), variable-element lists (for semiconductor layout), and the representations used by Glover and Grefenstette in this volume."
Some researchers have attempted to solve search and optimization problems using schemes patterned after evolution that employed mutation-plus-save-the-best strategies. Examples are Box (1957), Hicklin (1986), and the 1966 book by Fogel, Owens, and Walsh entitled Artificial Intelligence Through Simulated Evolution. The few results obtained from these efforts were highly specific to particular applications and domains and largely reflect the cleverness of implementation of the mutation concept rather than its usefulness as a general technique for achieving adaptive increases in fitness in populations. It is important to note that mutation is not the primary means by which biological populations in nature improve their fitness and it is not the primary means used in the present invention.
Since Holland's 1975 book, Holland and various colleagues have developed a novel application of conventional genetic algorithms called a "classifier system". A classifier system is a group of rules. Each rule consists of a conditional part and an action part (i.e. an IF-THEN rule). Both the conditional part and action part of each rule are like the individuals in the conventional genetic algorithm in that they are a strings of 0's and 1's of fixed length. In a classifier system, messages (consisting of binary strings) are received from the environment and activate those rules whose conditional part ("IF" part) match the message (binary string) coming in. This activation triggers the action part ("THEN" part) of the rule. The action part of a rule sends out a new message (binary string).
Classifier Systems are described in the 1978 article "Cognitive Systems based on Adaptive Algorithms" (by Holland and Judith S. Reitman) published in Pattern-Directed Inference Systems, edited by D. A. Waterman and Frederick Hayes-Roth; and David E. Goldberg's 1983 dissertation entitled Computer-Aided Gas Pipeline Operations Using Genetic Algorithms and Rule Learning. In classifier systems, credit is assigned to chains of individual rules that are invoked by a credit allocation scheme known as the "bucket brigade". The Holland process is a combination of a classifier system and a "bucket brigade algorithm". A 1987 paper by Cory Fujiki and John Dickinson in Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, (edited by John J. Grefenstette) describes a computer program for a classifier system written in LISP for solving the Prisoner's Dilemma using binary strings of fixed length and IF-THEN classifier rules.
We call conventional genetic algorithms "linear" because they manipulate strings (sequences) of characters over a fixed alphabet (typically strings of binary digits 0 and 1). This is in contrast to the "non-linear" situation in which the objects being manipulated are hierarchical expressions consisting of a hierarchical arrangement of functions and arguments.
The reasons for limiting the conventional genetic algorithm to binary strings of fixed length appear in the literature. First, in his 1983 disseration entitled Computer-Aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning, David E. Goldberg argues that any binary string of the common fixed length always has an interpretation (via a well-defined representation scheme) to the problem being solved. This might be called the property of being "well defined" and it is a desirable property.
Secondly, if each individual in the population consists of a binary string of fixed length, then the crossover operation will always produce another binary string of fixed length when applied to any two individuals in the population. This might be called a "closure" property and it is also a desirable property. Of course, binary strings of fixed length are not the only way of achieving these desirable properties of closure and being well-defined.
In Adaptation in Natural and Artificial Systems (1975, page 71), Holland argues in favor of strings consisting only of 0's and 1's (i.e. binary strings) in the conventional genetic algorithm on the basis that the number of strings in the search space that are searched automatically using what he calls the "implicit parallelism" of the conventional genetic algorithm is highest when the strings consist only of two possibilities. This point is true; however, it should not be the controlling consideration. For various reasons cited hereinafter, limiting the genetic algorithm to the one dimensional world of linear strings of fixed length (and, in particular, binary strings of fixed length) precludes solving many problems.
The field of computer science is replete with other situations where it is highly unrealistic to assume that the size or shape of a problem is known in advance to the solver so that he can use this information to rigidly pre-specify the size and shape of his search in advance. An elementary example from information theory illustrates this point. Huffman codes are binary strings of variable length that are used to maximize the amount of information that can be transmitted over a given channel. Huffman codes are somewhat similar to Morse code in that more frequent messages (letters, such as "e") are assigned codes of shorter length and less frequent messages are assigned codes of longer length. The Huffman coding algorithm starts with the messages that are to be transmitted and their probability of occurrence. The algorithm then assigns relatively short binary strings to the most frequent messages and relatively long binary strings to the rarer messages. The size of the strings needed in a Huffman coding scheme is not known in advance, but it is determined after applying the algorithm to the particular set of messages and their respective probabilities. Any attempt to decipher a Huffman code by searching and matching strings must take the length of longest binary strings actually used by the coding algorithm into account.
Using fixed length binary strings in conventional genetic algorithms limits their ability to solve many problems. The following 3 separate example problems illustrate additional limitations of conventional genetic algorithms.
First, suppose we want a computer to program itself to solve the problem of finding the point at which two intersecting straight lines intersect. The point of intersection of two straight lines is the pair of numbers that satisfy the two linear equations in two variables that represent the lines. Thus, the computer program we are seeking would use the coefficients of the two equations and various mathematical operators (such as multiplication, substraction, etc.) to produce the desired answer. To make the problem of having a computer learning to program itself more realistic, it is best not to specify in advance the size or shape of the mathematical expression needed to solve the problem. It is also more realistic if the computer had access to various irrelevant inputs and extraneous mathematical operations to confuse its search to find the solution to the problem.
There is no simple or convenient way to uniquely associate a binary string whose length is predetermined in advance with an arbitary mathematical expression composed of specified mathematical operations (functions) and arguments. A binary string of length n can only represent 2.sup.n different things (no matter what the representation scheme). No matter how large an n is preselected in advance, there are additional mathematical expressions.
Before continuing, it should be emphasized that it is not necessary to represent things of infinite size. Rather, what should be avoided is arbitrarily pre-setting a limit on the size and shape of the things being represented (even though any particular thing will itself be finite in size). In most problems, the size and shape of the solution are not necessarily known in advance. The process of solving the problem should be free to develop proposed solutions without any pre-set limit on the size and shape of the solution.
Even if an arbitrary maximum length specified in advance were acceptable, the method for associating each arbitrary mathematical expression (for example: A*B+C-D*E*F) with a binary string would necessarily obscure the underlying mathematical operations involved. The highly complex method used by Godel in 1931 in his proof of the Incompleteness Theorem is an example of such a method for making this kind of association. Thus, this first example problem highlights the need to be able to represent arbitrary mathematical expressions (involving various functions and arguments) whose length is not arbitrarily limited in advance (rather than merely strings of 0's and 1's of the same fixed length).
It should be noted that if it is assumed that the two straight lines in this problem always intersect, the problem is entirely numerical. However, if the two lines might possibly be parallel, the answer from a computer program to this expanded version of the problem might appropriately be a symbolic response (e.g. "The Equations are inconsistent and the lines are parallel") rather than the numeric location of the point of intersection. This situation can be easily recognized by a computer program by checking to see if a certain computed value (the determinant) is zero. Thus, this expanded version of this first example problem highlights the need occasionally to accommodate symbolic processing and symbolic output from a computer program that normally produces a numeric output.
Second, consider the problem of predicting the future elements of a sequence of numbers from a sampling of early numbers from the sequence. This problem is an example of induction. Induction is the logical process by which one observes specific examples of some process (e.g. "The sun has come up every morning so far during my life") and then "induces" a reasonable underlying rule for the process (e.g. "The sun always comes up in the morning"). In applying inductive reasoning, there is no proof that the result is correct. Nonetheless, the process of induction is very important and indeed lies at the heart of all learning.
In contrast, deduction is the logical process in which one starts with some given premises (or facts) and some deductive rules of inference and then reaches a logical conclusion by repeatedly applying the deductive rules to the original given premises or facts. The sequence of steps used in deduction to reach a conclusion is called the proof.
If one is given a sampling of a sequence of numbers such as 0, 2, 4, 6, 8, 10, 12, 14 it is not difficult to reasonably induce that the next number in the sequence is 16. The number 16 is a reasonable induction because each previous element of the sequence is 2 times the element's position in the sequence (counting the first element as position 0). Note, however, that even elements of this simple numerical sequence cannot be represented with strings whose length has been specified in advance.
More interesting sequences involve more complicated mathematical operations. For example, the 6th element of the sequence 2, 4, 8, 16, 32, can be expressed directly in mathematics as 2 raised to the 6th power (i.e. 64). This sequence can also be expressed in mathematics using a recursion--that is, by defining the 6th element in terms of previous element(s) in the sequence. In this case, the m.sup.th element of the sequence is 2 times element m-1 of the sequence (that is, 2 times 32 is 64).
For some important mathematical sequences, there is no known non-recursive expression for each element of the sequence, and the use of a recursion becomes a necessity, not merely an option. The well-known Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, is constructed by adding the 2 previous elements of sequence. For example, 8 is the sum of 3 and 5, and 13 is the sum of 5 and 8. In general, the m.sup.th element of the Fibonacci sequence is the sum of element m-1 and element m-2 of the sequence (with the understanding that the first two elements of the sequence are a "default" value of 1).
Thus, the problem of sequence induction highlights the need to be able to represent recursions as well as arbitrary mathematical expressions (involving functions and arguments). It also re-emphasizes the need to able to represent strings whose length has not been pre-specified in advance.
Third, consider the vexatious mathematical problem known as the Traveling Salesperson Problem. In this problem, the salesperson is given a mileage chart with the distances between a specified number of cities and is required to visit each of the cities once (and return home) while covering the least miles.
There is no known general mathematical formula giving the answer to this seemingly simple problem. There is no known general computational procedure (i.e. computer program, algorithm) to solve this problem (other than via "brute force": exhaustive evaluation of each of the alternative possible tours). The number of alternative possible tours is equal to the factorial of the number of cities. It is prohibitive for even the fastest computers to attempt to solve this problem in this way for even a relatively small number of cities. For example, for only 14 cities, there are 87,178,291,200 possible tours.
However, because of the practical significance of this kind of complex optimization problem (which has many equivalent industrial versions involving minimizing costs, times, and other resources), there is a vast literature describing past efforts to solve this problem, including various computational procedures that produce what appear to be reasonably good practical results within a reasonable amount of computer time. The 1985 book, The Traveling Salesman Problem by Eugene L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, is a recent summary of progress in research on this problem.
Intuitively, an especially natural way to attack the Traveling Salesperson Problem would seem to be to decompose the set of cities into smaller, more manageable sub-tours of cities; then, to find the best way of visiting all the cities in the sub-tour; and, finally, to find the best way of assembling the sub-tours into one grand tour. For example, if state capitals are being visited, it seems clear that one should consider the 6 state capitals in New England as a sub-tour beginning in Hartford, Connecticut and ending in Montpelier, Vermont and to then analyze how to best visit the 4 other cities within the sub-tour. On the other hand, it is far from clear in advance as to what size sub-tour or which cities belong in the best sub-tour involving the state capitals in the Midwest. Indeed, any attempt to arbitrarily pre-specify either sub-tour size or sub-tour contents in advance would seem likely to preclude finding the overall best solution.
Thus, the Traveling Salesperson Problem highlights the need to represent an arbitrary set of items with no duplicates (i.e. permutations) and various arbitrary sub-sets of such items of arbitrarily varying size. It also highlights the need to be able to develop hierarchies in which solutions to sub-problems are manipulated and assembled hierarchically into solutions to the original main problem.
In fact, many mathematical problems are solved by first "decomposing" a larger problem into smaller sub-problems. Then, an attempt is made to solve each of the sub-problems. And, finally, the solutions to the sub-problems are assembled into a solution to the original problem. The problem of solving sets of a large number of equations with many variables and solving polynomial equations of high order are examples of problems where decomposition can be used.
In some cases, there is a symmetry between this process of assembly and the solution to the individual sub-problem. That is, in this assembly process, the solutions to the sub-problems may be manipulated as if they themselves were merely the elements of a sub-problem. In the case of the Traveling Salesperson Problem, for example, the process of combining the sub-tours into one grand tour might involve treating each of the sub-tours as if it were merely a single city (i.e. the basic element of a sub-tour) and then trying to find the best way to visit those "cities". This kind of symmetry often develops when problems are solved by decomposition.
Even when no symmetry is involved, a "hierarchy" develops when a problem is solved by decomposition. At the lowest level of the hierarchy, the sub-problem is solved. The hierarchy consists of combining the solutions of the sub-problem into the solution to the larger problem. Something similar is commonplace in computer programming in general. For example, sub-routines (or sub-procedures) are typically called by a main program. The main program is at the top of the hierarchy, typically organized to provide an overview of the solution to the whole problem. Each of the sub-routines called by the main program are found at one level lower on the hierarchy. If one of the sub-routines itself happens to call upon another sub-routine, that second sub-routine is one level lower on the hierarchy than the sub-routine which called it. Complex social organizations (such as corporations and military organizations), are similarly organized into hierarchies.
The ability to decompose problems into hierarchies of sub-problems is generally important for solving problems. A significant fraction of the papers found in the 1985 and 1987 Proceedings of the International Conference on Genetic Algorithms and their Applications, and other articles in the literature, discuss the difficulties of applying the conventional genetic algorithm to the Traveling Salesperson Problem and other problems involving permutations.
What is needed is a way to apply some of the general principles of biological natural selection that are embodied in the conventional genetic algorithm (i.e. survival of the fittest and crossing over of parents' traits to offspring) to a greatly expanded class of problems. In particular, what is needed is a method for adaptively creating computer programs involving complicated combinations of mathematical functions and their arguments, recursions, symbolic processing, and other complicated data structures (such as permutations) with no advance limitations on the size, shape, or complexity of the programs. One object of the present invention is to provide a genetic algorithm to provide solutions for an expanded class of problems. A further object of the present invention is to provide a genetic algorithm process without any predetermined limits on the size, shape, or complexity of the members of the subject population.